import { BinaryTree, BinaryTreeNode, defaultCompare } from "./BinaryTree";

/**
 * 自平衡树
 */
export default class AVLTree extends BinaryTree{
    public constructor(compareFn = defaultCompare){
        super(compareFn);
    }
    public getNodeHeight(node:BinaryTreeNode):number{
        if(node == null){
            return -1;
        }
        return Math.max(this.getNodeHeight(node.left),this.getNodeHeight(node.right))+1;
    }
    /**
     * 左旋转
     * @param node 
     * @returns 
     */
    public rotationLL(node:BinaryTreeNode):BinaryTreeNode{
        const temp = node.left;
        node.left = temp.right;
        temp.right = node;
        return temp;
    }
    /**
     * 右旋转
     * @param node 
     * @returns 
     */
    public rotationRR(node:BinaryTreeNode):BinaryTreeNode{
        const temp = node.right;
        node.right = temp.left;
        temp.left = node;
        return temp;
    }
    public rotationLR(node:BinaryTreeNode):BinaryTreeNode{
        node.left = this.rotationRR(node.left);
        return this.rotationLL(node);
    }
    public rotationRL(node:BinaryTreeNode):BinaryTreeNode{
        node.right = this.rotationLL(node.right);
        return this.rotationRR(node);
    }
}